/*
面试题 03.04. 化栈为队
232. 用栈实现队列
*/

typedef struct {
    int top1; //栈1的栈顶指针
    int top2; //栈2的栈顶指针
    int size; //栈的大小
    int count; //队列中的元素个数
    int *S1; //栈1
    int *S2; //栈2
} MyQueue;

/** Initialize your data structure here. */
//初始化两个栈
MyQueue* myQueueCreate() {
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    queue->top1 = -1;
    queue->top2 = -1;
    queue->size = 100;
    queue->count = 0;  //队列中当前元素个数0
    queue->S1 = (int*)malloc(queue->size * sizeof(int));
    queue->S2 = (int*)malloc(queue->size * sizeof(int));

    return queue;
}

/*
栈1只进行入栈操作，相当于入队
假设入栈顺序为：1，2，3，4
栈1保存为：4，3，2，1
出栈顺序：4，3，2，1
*/
void myQueuePush(MyQueue* obj, int x) {
    obj->S1[++obj->top1] = x; //新元素入栈相当于入队
    
    obj->count++; //队列元素个数加一
}

/*
栈2只进行出栈，相当于出队操作
将栈1的元素转存到栈2，栈2的顺序为：1，2，3，4
栈2出栈顺序为：1，2，3，4
和队列的入队、出队模式相同
*/
int myQueuePop(MyQueue* obj) {
    if(obj->top2 == -1)
    {
        while(obj->top1 != -1)
        {
            obj->S2[++obj->top2] = obj->S1[obj->top1--]; //将栈1中的元素保存到栈2中
        }
    }
    obj->count--;
    return obj->S2[obj->top2--];

}

/*查看队头元素，即查看栈2的栈顶元素*/
int myQueuePeek(MyQueue* obj) {
    if(obj->top2 == -1)
    {
        while(obj->top1 != -1)
        {
            obj->S2[++obj->top2] = obj->S1[obj->top1--];
        }
    }
    return obj->S2[obj->top2];
}

/*队列为空返回true，否则返回false */
bool myQueueEmpty(MyQueue* obj) {
    if(obj->count == 0)
        return true;
    else
        return false;
}

void myQueueFree(MyQueue* obj) {
    free(obj->S1);
    free(obj->S2);
    free(obj);
}
